Next: Composing Patterns in Rewrite Rules, Previous: Algebraic Properties of Rewrite Rules, Up: Rewrite Rules
Certain “function names” serve as markers in rewrite rules. Here is a complete list of these markers. First are listed the markers that work inside a pattern; then come the markers that work in the righthand side of a rule.
One kind of marker, ‘import(x)’, takes the place of a whole rule. Here ‘x’ is the name of a variable containing another rule set; those rules are “spliced into” the rule set that imports them. For example, if ‘[f(a+b) := f(a) + f(b), f(a b) := a f(b) :: real(a)]’ is stored in variable ‘linearF’, then the rule set ‘[f(0) := 0, import(linearF)]’ will apply all three rules. It is possible to modify the imported rules slightly: ‘import(x, v1, x1, v2, x2, ...)’ imports the rule set ‘x’ with all occurrences of ‘v1’, as either a variable name or a function name, replaced with ‘x1’ and so on. (If ‘v1’ is used as a function name, then ‘x1’ must be either a function name itself or a ‘< >’ nameless function; see Specifying Operators.) For example, ‘[g(0) := 0, import(linearF, f, g)]’ applies the linearity rules to the function ‘g’ instead of ‘f’. Imports can be nested, but the import-with-renaming feature may fail to rename sub-imports properly.
The special functions allowed in patterns are:
quote, the arguments
‘x1,x2,...’
are treated as patterns. If you wish them to be treated
“plainly” as well, you must enclose them with more
plain markers: ‘plain(plain(-a) + plain(b
c))’.For general miscellaneous functions, the default value
def must be specified. Optional arguments are
dropped starting with the rightmost one during matching. For
example, the pattern ‘f(opt(a,0), b, opt(c,b))’ will
match ‘f(b)’, ‘f(a,b)’, or
‘f(a,b,c)’. Default values of zero
and ‘b’
are supplied in this example for the omitted arguments. Note
that the literal variable ‘b’ will be the default in the
latter case, not the value that matched the
meta-variable ‘b’. In other words, the default
def is effectively quoted.
cons, except that the last element is
matched to ‘h’, with the remaining elements
matched to ‘t’.apply pattern. For example,
‘apply(f,x)’ matches any function
call, ‘apply(quote(f),x)’ matches any
call to the function ‘f’, ‘apply(f,[a,b])’ matches any
function call with exactly two arguments, and
‘apply(quote(f),
cons(a,cons(b,x)))’ matches any call to
the function ‘f’ with two or more arguments.
Another way to implement the latter, if the rest of the rule
does not need to refer to the first two arguments of
‘f’ by
name, would be ‘apply(quote(f), x :: vlen(x) >=
2)’. Here's a more interesting sample use
of apply:
apply(f,[x+n]) := n + apply(f,[x])
:: in(f, [floor,ceil,round,trunc]) :: integer(n)
Note, however, that this will be slower to match than a
rule set with four separate rules. The reason is that Calc
sorts the rules of a rule set according to top-level function
name; if the top-level function is apply, Calc
must try the rule for every single formula and sub-formula.
If the top-level function in the pattern is, say,
floor, then Calc invokes the rule only for
sub-formulas which are calls to floor.
Formulas normally written with operators like
+ are still considered function calls:
apply(f,x) matches ‘a+b’ with
‘f = add’,
‘x =
[a,b]’.
You must use apply for meta-variables with
function names on both sides of a rewrite rule:
‘apply(f, [x]) :=
f(x+1)’ is not correct, because
it rewrites ‘spam(6)’ into
‘f(7)’.
The righthand side should be ‘apply(f, [x+1])’. Also note that
you will have to use No-Simplify mode (m O) when
entering this rule so that the apply isn't
evaluated immediately to get the new rule
‘f(x) :=
f(x+1)’. Or, use s e to enter
the rule without going through the stack, or enter the rule
as ‘apply(f, [x]) := apply(f,
[x+1]) :: 1’. See
Conditional
Rewrite Rules.
Special functions for the righthand sides of rules are:
quote is invisible. However,
quote has the special property in Calc that its
argument is not evaluated. Thus, while it will not work to put
the rule ‘t(a) :=
typeof(a)’ on the stack because
‘typeof(a)’
is evaluated immediately to produce ‘t(a) := 100’, you can use
quote to protect the righthand side:
‘t(a) :=
quote(typeof(a))’. (See Conditional
Rewrite Rules, for another trick for protecting rules from
evaluation.)plain is
useful is the rule, ‘q(x) :=
quote(x)’, trying to expand a shorthand
notation for the quote function. This rule will
not work as shown; instead of replacing
‘q(foo)’
with ‘quote(foo)’, it will replace it with
‘foo’! The
correct rule would be ‘q(x) :=
plain(quote(x))’.cons is a regular Calc function which normally
does this anyway; the only way cons is treated
specially by rewrites is that cons on the
righthand side of a rule will be evaluated even if default
simplifications have been turned off.cons except putting
‘h’ at the
end of the vector ‘t’.apply is also a regular Calc
function.cons and apply are always treated.
However, there is a slight difference:
‘cons(2+3,
[])’ with default simplifications off will
be converted to ‘[2+3]’, whereas
‘eval(cons(2+3,
[]))’ will be converted to
‘[5]’.There are also some special functions you can use in conditions.
evalsimp or
evalextsimp as described above to invoke higher
levels of simplification. The result of
‘x’ is
then bound to the meta-variable ‘v’. As usual, if this
meta-variable has already been matched to something else the
two values must be equal; if the meta-variable is new then it
is bound to the result of the expression. This variable can
then appear in later conditions, and on the righthand side of
the rule. In fact, ‘v’ may be any pattern in which
case the result of evaluating ‘x’ is matched to that pattern,
binding any meta-variables that appear in that pattern. Note
that let can only appear by itself as a
condition, or as one term of an ‘&&’ which is a whole
condition: It cannot be inside an ‘||’ term or otherwise buried.
The alternate, equivalent form ‘let(v, x)’ is also recognized.
Note that the use of ‘:=’ by let, while
still being assignment-like in character, is unrelated to the
use of ‘:=’ in the main part of a rewrite
rule.
As an example, ‘f(a) :=
g(ia) :: let(ia := 1/a) :: constant(ia)’
replaces ‘f(a)’ with
‘g’ of the
inverse of ‘a’, if that inverse exists and is
constant. For example, if ‘a’ is a singular matrix the
operation ‘1/a’ is left unsimplified and
‘constant(ia)’ fails, but if
‘a’ is an
invertible matrix then the rule succeeds. Without
let there would be no way to express this rule
that didn't have to invert the matrix twice. Note that,
because the meta-variable ‘ia’ is otherwise unbound in this
rule, the let condition itself always
“succeeds” because no matter what
‘1/a’
evaluates to, it can successfully be bound to
ia.
Here's another example, for integrating cosines of linear
terms: ‘myint(cos(y),x) :=
sin(y)/b :: let([a,b,x] := lin(y,x))’.
The lin function returns a 3-vector if its
argument is linear, or leaves itself unevaluated if not. But
an unevaluated lin call will not match the
3-vector on the lefthand side of the let, so
this let both verifies that y is
linear, and binds the coefficients a and
b for use elsewhere in the rule. (It would have
been possible to use ‘sin(a x
+ b)/b’ for the righthand side instead,
but using ‘sin(y)/b’ avoids gratuitous
rearrangement of the argument of the sine.)
Similarly, here is a rule that
implements an inverse-erf function. It uses
root to search for a solution. If
root succeeds, it will return a vector of two
numbers where the first number is the desired solution. If no
solution is found, root remains in symbolic
form. So we use let to check that the result was
indeed a vector.
ierf(x) := y :: let([y,z] := root(erf(a) = x, a, .5))
matches is a
standard Calc function, it can appear anywhere in a
condition. But if it appears alone or as a term of a
top-level ‘&&’, then you get the
special extra feature that meta-variables which are bound to
things inside p can be used elsewhere in the
surrounding rewrite rule.
The only real difference between ‘let(p := v)’ and
‘matches(v,
p)’ is that the former evaluates
‘v’ using
the default simplifications, while the latter does
not.
remember appears as a condition in
a rule, then when that rule succeeds the original expression
and rewritten expression are added to the front of the rule
set that contained the rule. If the rule set was not stored
in a variable, remember is ignored. The lefthand
side is enclosed in quote in the added rule if
it contains any variables.
For example, the rule ‘f(n)
:= n f(n-1) :: remember’ applied to
‘f(7)’
will add the rule ‘f(7) := 7
f(6)’ to the front of the rule set. The
rule set EvalRules works slightly differently:
There, the evaluation of ‘f(6)’ will complete before the
result is added to the rule set, in this case as
‘f(7) :=
5040’. Thus remember is most
useful inside EvalRules.
It is up to you to ensure that the optimization performed
by remember is safe. For example, the rule
‘foo(n) := n :: evalv(eatfoo)
> 0 :: remember’ is a bad idea
(evalv is the function equivalent of the
= command); if the variable eatfoo
ever contains 1, rules like ‘foo(7) := 7’ will be added to the
rule set and will continue to operate even if
eatfoo is later changed to 0.